//You are given an integer array nums and an integer target. 
//
// You want to build an expression out of nums by adding one of the symbols '+' 
//and '-' before each integer in nums and then concatenate all the integers. 
//
// 
// For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 
//and concatenate them to build the expression "+2-1". 
// 
//
// Return the number of different expressions that you can build, which 
//evaluates to target. 
//
// 
// Example 1: 
//
// 
//Input: nums = [1,1,1,1,1], target = 3
//Output: 5
//Explanation: There are 5 ways to assign symbols to make the sum of nums be 
//target 3.
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// Example 2: 
//
// 
//Input: nums = [1], target = 1
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
// Related Topics Array Dynamic Programming Backtracking 👍 5462 👎 214


package leetcode.editor.en;

public class _494_TargetSum {
    public static void main(String[] args) {
        Solution solution = new _494_TargetSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum+=nums[i];
            }
            if (Math.abs(target)>Math.abs(sum)) {
                return 0;
            }
            int t = sum*2+1;
            int [][] dp = new int[nums.length][t];
            if (nums[0]==0){
                dp[0][sum] = 2;
            }else {
                dp[0][sum+nums[0]] = 1;
                dp[0][sum-nums[0]] = 1;
            }
            for (int i = 1; i < nums.length; i++) {
                for (int j = 0; j < t; j++) {
                    int l = Math.max(j - nums[i], 0);
                    int r = j+nums[i]<t?j+nums[i]:0;
                    dp[i][j] = dp[i-1][l]+dp[i-1][r];
                }
            }
            return dp[nums.length-1][sum+target];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}